package E_2024;

import java.util.ArrayList;
import java.util.List;

/*
        吃货和"馋嘴"两人到披萨店点了一份铁盘圆形披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的 服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。
        由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法:从"吃货"开始，轮流取被萨。除了第一块破产可以任意选取外，其他都必须从缺口开始选
        他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货”知道"馋嘴"的想法。
        已知披萨小块的数量以及每块的大小，求”吃货”能分得的最大的披萨大小的总和。
    输入描述
        第 1行为一个正整数奇数 N，表示披萨小块数量.
        3≤N<500
        接下来的第 2 行到第 N + 1行(共 N 行)，每行为一个正整数，表示第i块披萨的大小
        1≤ i ≤N
        披萨小块从某一块开始，按照一个方向次序顺序编号为 1~N
    每块披萨的大小范围为[1,2147483647]
    输出描述
        "吃货”能分得到的最大的披萨大小的总和。
 */
public class E_100_13 {
    public static void main(String[] args) {
        System.out.println(ans2(new int[]{5,3,1,7,9,1,2}));
    }
    public static int ans(int[] pes){
        int max = 0;
        // 选择开始的起点
        for (int i = 0; i < pes.length; i++) {
            int left = i-1 < 0 ? pes.length-1 : i-1;
            int right = i+1 == pes.length ? 0 : i+1;
            // 第一次由 吃货 进行选择
            int temp = pes[i];
            // 每次操作取走两块披萨，pizza的总数的一半就是需要操作的次数;
            int x = (pes.length - 1) >> 1;
            while(x-- > 0){
                // 吃货 选择后由 馋嘴 选择，选择后需要将对应下标移动一位
                if (pes[right] > pes[left])
                    right = right+1 == pes.length ? 0 : right+1;
                else
                    left = left-1 < 0 ? pes.length-1 : left-1;
                // 馋嘴 选择完成后继续由 吃货 选择，选择策略
                if (pes[right] > pes[left]) {
                    temp += pes[right];
                    right = right + 1 == pes.length ? 0 : right + 1;
                }else {
                    temp += pes[left];
                    left = left - 1 < 0 ? pes.length - 1 : left - 1;
                }
            }
            max = Math.max(max,temp);
        }
        return max;
    }
    public static int ans2(int[] pizza){
        int maxSum = 0;
        for (int i = 0; i < pizza.length; i++) {
            List<Integer> remaining = new ArrayList<>();
            // 构造剩余的披萨块序列
            for (int j = i + 1; j < pizza.length; j++) {
                remaining.add(pizza[j]);
            }
            for (int j = 0; j < i; j++) {
                remaining.add(pizza[j]);
            }
            int currentSum = pizza[i] + simulate(remaining);
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        return maxSum;
    }

    private static int simulate(List<Integer> remaining) {
        int left = 0;
        int right = remaining.size() - 1;
        int sumEater = 0;
        int turn = 0; // 0表示馋嘴的回合，1表示吃货的回合

        while (left <= right) {
            int selected;
            if (remaining.get(left) > remaining.get(right)) {
                selected = left;
            } else {
                selected = right;
            }

            int value = remaining.get(selected);
            if (turn % 2 == 1) { // 吃货的回合
                sumEater += value;
            }

            if (selected == left) {
                left++;
            } else {
                right--;
            }

            turn++;
        }
        return sumEater;
    }
}
